package com.gxc.string;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右括号，返回公式的计算结果。
 * [举例]
 * str=”48*((70-65)-43)+8*1”，返回-1816。
 * str="3+1*4"，返回7。
 * str="3+(1*4)"，返回7。
 * [说明]
 * 1，可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。
 * 2.如果是负数，就需要用括号括起来，比如”4*(-3)”。
 * 但如果负数作为公式的开头或括号部分的开头，则可以没有括号，比如”-3*4”和”(-3*4)“都是合法的。
 * 3，不用考虑计算过程中会发生溢出的情况。
 *
 * 解法：
 * 准备一个栈(队列)，
 * 符号分成两种加减符号和乘除符号，
 * 遇到加减符号直接加入栈内，
 * 遇到乘除符号先加入栈，等遇到下一个加减符号时，倒出栈内数据直到遇到加减符号（乘除先做运算），计算完结果加入栈
 * 遇到左括号，直接加入栈内，遇到右括号时，倒出栈内数据直到遇到第一个左括号，计算括号内数据，计算完结果加入栈
 * 最后倒出数据，加减运算
 */
public class Calculate {

    public static void main(String[] args) {
        System.out.println(calculate(("(1+(4+5+2)-3)+(6+8)")));
    }

    public static int process(String str) {
        LinkedList<String> queue = new LinkedList<>();


        for (int i = 0; i < str.length(); i++) {
            //运算符
            if (isSpecialSharacter(str.charAt(i))) {
                queue.add(str.charAt(i) + "");
            } else {
                int start = i;
                while (i<str.length() && !isSpecialSharacter(str.charAt(i))) {
                    i++;
                }
                queue.add(str.substring(start, i));
                i--;
            }
        }

        return computeParenthesis(queue);
    }

    public static int process2(String str) {
        return value(str.toCharArray(), 0)[0];
    }

    //递归过程，返回值为数组，长度为2arr[0]代表计算结果，arr[1]代表计算到的位置
    //i表示当前计算的位置
    public static int[] value(char[] str, int i) {
        //用一个双向链表进行收集，即分析中的栈
        LinkedList<String> que = new LinkedList<String>();
        int pre = 0;
        int[] bra = null;
        while (i < str.length && str[i] != ')') {
            if (str[i] >= '0' && str[i] <= '9') { //当一直遇到数字时转换成可以计算的类型
                pre = pre * 10 + str[i++] - '0';
            } else if (str[i] != '(') { //遇到的不是数字且不是左括号即遇到了加减乘除
                addNum(que, pre);
                que.addLast(String.valueOf(str[i++]));
                pre = 0;
            } else {//遇到了左括号，进入递归。计算括号内的值
                bra = value(str, i + 1);
                pre = bra[0];
                i = bra[1] + 1;//跳过左括号的位置
            }
        }
        addNum(que, pre);
        return new int[] { getNum(que), i };
    }

    public static void addNum(LinkedList<String> que, int num) {
        if (!que.isEmpty()) {
            int cur = 0;
            String top = que.pollLast();
            if (top.equals("+") || top.equals("-")) {
                que.addLast(top);
            } else {
                cur = java.lang.Integer.valueOf(que.pollLast());
                num = top.equals("*") ? (cur * num) : (cur / num);
            }
        }
        que.addLast(String.valueOf(num));
    }

    public static int getNum(LinkedList<String> que) {
        int res = 0;
        boolean add = true;
        String cur = null;
        int num = 0;
        while (!que.isEmpty()) {
            cur = que.pollFirst();
            if (cur.equals("+")) {
                add = true;
            } else if (cur.equals("-")) {
                add = false;
            } else {
                num = java.lang.Integer.valueOf(cur);
                res += add ? num : (-num);
            }
        }
        return res;
    }

    private static boolean isSpecialSharacter(char c) {
        if (c == '+' || c == '-' || c == '*'
                || c == '/' || c == '(' || c ==')') return true;
        return false;
    }

    /**
     * 计算括号内数据
     * @param queue
     * @return
     */
    public static int computeParenthesis(LinkedList<String> queue) {
        LinkedList<String> noParenthesis = new LinkedList<>();

        while (!queue.isEmpty()) {
            String pop = queue.pop();
            if (pop.equals(")")) {
                LinkedList<String> noParenthesis2 = new LinkedList<>();
                while (!noParenthesis.peekLast().equals("(")) {
                    noParenthesis2.add(noParenthesis.pollLast());
                }
                //删除与 ）匹配的（
                noParenthesis.pollLast();

                //倒序  65-70  变成  70-65
                LinkedList<String> noParenthesis3 = new LinkedList<>();
                while (!noParenthesis2.isEmpty()) {
                    noParenthesis3.add(noParenthesis2.pollLast());
                }

                int sum = computeMultiply_Divide(noParenthesis3);
                noParenthesis.add(sum + "");
            } else {
                noParenthesis.add(pop);
            }
        }

        return computeMultiply_Divide(noParenthesis);
    }

    /**
     * 计算乘除法
     * @param queue
     * @return
     */
    public static int computeMultiply_Divide(LinkedList<String> queue) {
        LinkedList<String> noMultiply_Divide = new LinkedList<>();

        while (!queue.isEmpty()) {
            String pop = queue.pop();
            if (pop.equals("*") || pop.equals("/")) {
                String num2 = noMultiply_Divide.pollLast();
                int num = 0;
                if (pop.equals("*")) {
                    num = java.lang.Integer.parseInt(queue.pop()) * java.lang.Integer.parseInt(num2);
                } else if (pop.equals("/")) {
                    num = java.lang.Integer.parseInt(queue.pop()) / java.lang.Integer.parseInt(num2);
                }
                noMultiply_Divide.add(num + "");
            } else {
                noMultiply_Divide.add(pop);
            }
        }

        return computeAdd_Subtract(noMultiply_Divide);
    }

    /**
     * 计算加减法
     * @param queue
     * @return
     */
    private static int computeAdd_Subtract(LinkedList<String> queue) {
        int sum = 0;

        while (!queue.isEmpty()) {
            String pop = queue.pop();
            if (pop.equals("-")) {
                String num2 = queue.pop();
                sum = sum - java.lang.Integer.parseInt(num2);
            } else if (pop.equals("+")){
                String num2 = queue.pop();
                sum = sum +  java.lang.Integer.parseInt(num2);
            } else {
                sum = sum +  java.lang.Integer.parseInt(pop);
            }
        }
        return sum;
    }

    public static int calculate(String s) {
        Deque<String> stack = new LinkedList<>();

        char[] charArray = s.toCharArray();
        int index = 0;
        while (index < charArray.length) {
            char c = charArray[index];
            if (c == ' ') {
                index++;
                continue;
            }
            if (isSpecialSharacter(c)) {
                stack.offer(c + "");
                index++;
            } else {
                int start = index;
                while (index < charArray.length && !isSpecialSharacter(charArray[index]) && charArray[index]!=' ') {
                    index++;
                }
                stack.offer(s.substring(start, index));
            }
        }
        return handleParentheses(stack);
    }

    private static int handleParentheses(Deque<String> stack) {
        Deque<String> noParentheses = new LinkedList<>();

        while (!stack.isEmpty()) {
            String s = stack.pollLast();
            if (s.equals(")")) {
                Deque<String> recursion = new LinkedList<>();
                while (!stack.peekLast().equals("(")) {
                    recursion.offerFirst(stack.pollLast());
                }

                stack.pollLast();
                int sum =  handleParentheses(recursion);
                noParentheses.offerFirst(sum + "");
            } else {
                noParentheses.offerFirst(s);
            }
        }
        return handleMultiplicationAndDivision(noParentheses);
    }

    private static int handleMultiplicationAndDivision(Deque<String> stack) {
        Deque<String> noMultiplicationAndDivision = new LinkedList<>();
        while (!stack.isEmpty()) {
            String s = stack.pollLast();
            if (s.equals("*") || s.equals("/")) {
                int x = java.lang.Integer.parseInt(s);
                int y = java.lang.Integer.parseInt(noMultiplicationAndDivision.pollFirst());

                if (s.equals("*")) {
                    noMultiplicationAndDivision.offerFirst(x * y + "");
                } else {
                    noMultiplicationAndDivision.offerFirst(x /y + "");
                }
            } else {
                noMultiplicationAndDivision.offerFirst(s);
            }
        }
        return handleAdditionAndSubtraction(noMultiplicationAndDivision);
    }

    private static int handleAdditionAndSubtraction(Deque<String> stack) {
        int sum = stack.peekFirst().equals("-")?0: java.lang.Integer.parseInt(stack.pollFirst());
        while (!stack.isEmpty()) {
            String s = stack.pollFirst();
            if (s.equals("+")) {
                sum += java.lang.Integer.parseInt(stack.pollFirst());
            } else {
                sum -= java.lang.Integer.parseInt(stack.pollFirst());
            }
        }
        return sum;
    }

}
